package com.lft.ten_commonly_used_algorithms09.floyd;

/**
 * 弗洛伊德算法
 */
public class FloydAlgorithmDemo {
	public static void main(String[] args) {
		char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		final int N = Integer.MAX_VALUE;
		int[][] matrix = {
				{N, 5, 7, N, N, N, 2},
				{5, N, N, 9, N, N, 3},
				{7, N, N, N, 8, N, N},
				{N, 9, N, N, N, 4, N},
				{N, N, 8, N, N, 5, 4},
				{N, N, N, 4, 5, N, 6},
				{2, 3, N, N, 4, 6, N}};
		Graph graph = new Graph(matrix, vertexes);
		graph.floyd();
		graph.show();
		graph.printShortestPathOne(3, 2);
		System.out.println("======");
		graph.printShortestPathAll();
	}
}

/**
 * 图类
 */
class Graph {
	/**
	 * 顶点数组
	 */
	char[] vertex;
	/**
	 * 保存各顶点最短距离的矩阵。
	 */
	int[][] dis;
	/**
	 * 保存各顶点至目标顶点的访问路径矩阵
	 */
	int[][] path;
	
	/**
	 * 构造器
	 * @param numOfVertexes 顶点数量
	 * @param matrix        邻接矩阵
	 * @param vertex        顶点数组
	 */
	public Graph(int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				this.dis[i][j] = matrix[i][j] == 0 ? Integer.MAX_VALUE : matrix[i][j];
			}
		}
		this.path = new int[vertex.length][vertex.length];
		// 对 path 数组进行初始化
		for (int i = 0; i < vertex.length; i++) {
			for (int j = 0; j < vertex.length; j++) {
				this.path[i][j] = j;
			}
		}
	}
	
	/**
	 * 弗洛伊德算法方法
	 */
	public void floyd() {
		int min;
		for (int mid = 0; mid < vertex.length; mid++) {
			for (int start = 0; start < vertex.length; start++) {
				for (int target = 0; target < vertex.length; target++) {
					min = (dis[start][mid] == Integer.MAX_VALUE || dis[mid][target] == Integer.MAX_VALUE)
							?
							Integer.MAX_VALUE
							:
							dis[start][mid] + dis[mid][target];
					if (dis[start][target] > min) {
						dis[start][target] = min;
						path[start][target] = path[start][mid];
					}
				}
			}
		}
	}
	
	/**
	 * 显示 dis 数组 path 数组
	 */
	public void show() {
		System.out.println("D矩阵：");
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis.length; j++) {
				System.out.printf("%3d", dis[i][j]);
			}
			System.out.println();
		}
		System.out.println("P矩阵：");
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path.length; j++) {
				System.out.printf("%3d", path[i][j]);
			}
			System.out.println();
		}
	}
	
	public void printShortestPathOne(int row, int col) {
		if (row == col) {
			System.out.println("< " + vertex[row] + " -> " + vertex[col] + " >, ~~~没有最短路径~~~");
		} else {
			System.out.println("< " + vertex[row] + " -> " + vertex[col] + " >, 最短路径距离为:" + dis[row][col]);
			System.out.print("路线为：" + vertex[row] + " -> ");
			int mid = path[row][col];
			while (mid != col) {
				System.out.print(vertex[mid] + " -> ");
				mid = path[mid][col];
			}
			System.out.println(vertex[col]);
		}
	}
	
	public void printShortestPathAll() {
		int row = 0;
		int col = 0;
		int mid = 0;
		for (row = 0; row < vertex.length; row++) {
			for (col = 0; col < vertex.length; col++) {
				if (row == col) {
					System.out.println("< " + vertex[row] + " -> " + vertex[col] + " >, ~~~没有最短路径~~~");
				} else {
					System.out.println("< " + vertex[row] + " -> " + vertex[col] + " >, 最短路径距离为:" + dis[row][col]);
					System.out.print("路线为：" + vertex[row] + " -> ");
					mid = path[row][col];
					while (mid != col) {
						System.out.print(vertex[mid] + " -> ");
						mid = path[mid][col];
					}
					System.out.println(vertex[col]);
				}
			}
			System.out.println();
		}
	}
}